//
//  Problem1638.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/4/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1638. 统计只差一个字符的子串数目
 给你两个字符串 s 和 t ，请你找出 s 中的非空子串的数目，这些子串满足替换 一个不同字符 以后，是 t 串的子串。换言之，请你找到 s 和 t 串中 恰好 只有一个字符不同的子字符串对的数目。

 比方说， "computer" 和 "computation" 加粗部分只有一个字符不同： 'e'/'a' ，所以这一对子字符串会给答案加 1 。

 请你返回满足上述条件的不同子字符串对数目。

 一个 子字符串 是一个字符串中连续的字符。

 示例 1：
     输入：s = "aba", t = "baba"
     输出：6
     解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
     ("aba", "baba")
     ("aba", "baba")
     ("aba", "baba")
     ("aba", "baba")
     ("aba", "baba")
     ("aba", "baba")
     加粗部分分别表示 s 和 t 串选出来的子字符串。
 示例 2：
     输入：s = "ab", t = "bb"
     输出：3
     解释：以下为只相差 1 个字符的 s 和 t 串的子字符串对：
     ("ab", "bb")
     ("ab", "bb")
     ("ab", "bb")
     加粗部分分别表示 s 和 t 串选出来的子字符串。
 示例 3：
     输入：s = "a", t = "a"
     输出：0
 示例 4：
     输入：s = "abe", t = "bbc"
     输出：10
 提示：
     1 <= s.length, t.length <= 100
     s 和 t 都只包含小写英文字母。
 */
@objcMembers class Problem1638: NSObject {
    func solution() {
        print(countSubstrings("aba", "baba"))
        print(countSubstrings("ab", "bb"))
        print(countSubstrings("a", "a"))
        print(countSubstrings("abe", "bbc"))
    }
    
    /*
     1: 遍历2个字符串，寻找不相同的字符，比如：s[i] != t[j] 个数+1
     2: 然后看计算i的左边有多个相同的：例如 aaab  aaac: 左边有3个相同，那么个数+3
     3: 然后看计算i的右边有多个相同的：例如 baaa  aaaa: 右边有3个相同，那么个数+3
     4: 还有计算左边*右边的个数：aba与aca： 个数 1 * 1
     */
    func countSubstrings(_ s: String, _ t: String) -> Int {
        if s.count == 0  || t.count == 0 {
            return 0
        }
        let sChart = Array(s)
        let tChart = Array(t)
        
        var result = 0
        for i in 0..<sChart.count {
            for j in 0..<tChart.count {
                if sChart[i] != tChart[j] {
                    var leftI = i - 1
                    var leftJ = j - 1
                    var rightI = i + 1
                    var rightJ = j + 1
                    
                    var leftNum = 0
                    while leftI >= 0, leftJ >= 0 {
                        if sChart[leftI] != tChart[leftJ] {
                            break
                        }
                        leftI -= 1
                        leftJ -= 1
                        leftNum += 1
                    }
                    
                    var rightNum = 0
                    while rightI < sChart.count, rightJ < tChart.count {
                        if sChart[rightI] != tChart[rightJ] {
                            break
                        }
                        rightI += 1
                        rightJ += 1
                        rightNum += 1
                    }
                    
                    result += (leftNum + rightNum + 1) + (leftNum * rightNum)
                }
            }
        }
        
        
        return result
    }
}
